//package bit2;
//
//
//import java.util.*;
//
//class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode() {}
//      TreeNode(int val) { this.val = val; }
//      TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;
//      }
//  }
//class AnnotatedNode {
//    TreeNode node;
//    int depth, pos;
//
//    AnnotatedNode(TreeNode n, int d, int p) {
//        node = n;
//        depth = d;
//        pos = p;
//    }
//}
//public class bitMain6 {
//
////    public static int widthOfBinaryTree(TreeNode root) {
////        Queue<AnnotatedNode> queue=new LinkedList<>();
////        queue.add(new AnnotatedNode(root,0,0));
////        int curDepth=0,left=0,right=0,width=0;
////        while (!queue.isEmpty()){
////            AnnotatedNode a=queue.poll();
////            if(a.node!=null){
////                queue.add(new AnnotatedNode(a.node.left,a.depth+1,a.pos*2));
////                queue.add(new AnnotatedNode(a.node.right,a.depth+1,a.pos*2+1));
////                if(curDepth!=a.depth){
////                    curDepth=a.depth;
////                    left=a.pos;
////                }
////                width=Math.max(width,a.pos-left+1);
////            }
////        }
////        return width;
////    }
//    public static List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> list=new ArrayList<>();
//        if(root==null){
//            return list;
//        }
//        Queue<TreeNode> queue=new LinkedList<>();
//        queue.offer(root);
//        while (queue.isEmpty()==false){
//            int size=queue.size();
//            List<Integer> list1=new ArrayList<>();
//            while (size>0){
//                TreeNode one=queue.poll();
//                if(one.left!=null){
//                    queue.offer(one.left);
//                }
//                if(one.right!=null){
//                    queue.offer(one.right);
//                }
//                list1.add(one.val);
//                size--;
//            }
//            list.add(list1);
//        }
//        return list;
//    }
//    public static boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree){
//        if(leftTree==null&&rightTree!=null||leftTree!=null&&rightTree==null){
//            return false;
//        }
//        if(leftTree==null&&rightTree==null){
//            return true;
//        }
//        if (leftTree.val!=rightTree.val){
//            return false;
//        }
//        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
//    }
//    public static boolean isSymmetric(TreeNode root) {
//        if (root==null){
//            return false;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//    public static int maxDepth(TreeNode root){
//        if(root==null){
//            return -1;
//        }
//        int left=maxDepth(root.left);
//        int right=maxDepth(root.right);
//        if(left>=0&&right>=0&&Math.abs(left-right)<=1){
//            return Math.max(left,right)+1;
//        }
//        return -1;
//    }
//    public static int maxDepth1(TreeNode root){
//        if(root==null){
//            return -1;
//        }
//        int left=maxDepth(root.left);
//        int right=maxDepth(root.right);
//        return Math.max(left,right)+1;
//    }
//    public static boolean isBalanced1(TreeNode root){
//        return maxDepth(root)>0;
//    }
//    public static boolean isBalanced(TreeNode root) {
//        if (root==null){
//            return true;
//        }
//        int left=maxDepth(root.left);
//        int right=maxDepth(root.right);
//        if (Math.abs(left-right)<=1&&isBalanced(root.right)&&isBalanced(root.left)){
//            return true;
//        }
//        return false;
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root==null){
//            return false;
//        }
//        if(isSameTree(root,subRoot)){
//            return true;
//        }
//        if (isSubtree(root.left,subRoot)){
//            return true;
//        }
//        if(isSubtree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p==null&&q==null){
//            return true;
//        }
//        if(p!=null&&q==null){
//            return false;
//        }
//        if(p==null&&q!=null){
//            return false;
//        }
//        if(p.val!=q.val){
//            return false;
//        }
//        if(isSameTree(p.left,q.left)&&isSameTree(p.right,q.right)){
//            return true;
//        }
//        return false;
//    }
//    public static int widthOfBinaryTree(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        Queue<TreeNode> one=new LinkedList<>();
//
//    }
//    public static boolean isCompleteTree(TreeNode root) {
//        Queue<TreeNode> one=new LinkedList<>();
//        if (root==null){
//            return true;
//        }
//        one.offer(root);
//        while (!one.isEmpty()){
//            TreeNode node= one.poll();
//            if(node==null){
//                break;
//            }
//            one.offer(node.left);
//            one.offer(node.right);
//        }
//        while (!one.isEmpty()){
//            TreeNode node=one.poll();
//            if(node!=null){
//                return false;
//            }
//        }
//        return true;
//    }
//    public static void main(String[] args) {
//
//    }
//}
